/*
 * @lc app=leetcode.cn id=676 lang=typescript
 *
 * [676] 实现一个魔法字典
 */

// @lc code=start

class TireNode676 {
  public children: Map<string, TireNode676>;
  public isWord: boolean;
  constructor() {
    this.children = new Map();
    this.isWord = false;
  }
}

class Tire676 {
  private root: TireNode676;
  constructor() {
    this.root = new TireNode676();
  }

  insert(word: string) {
    let node = this.root;
    for (let char of word) {
      if (!node.children.has(char)) {
        node.children.set(char, new TireNode676());
      }
      node = node.children.get(char);
    }
    node.isWord = true;
  }
  private _search(word: string, pos: number, n: number, node: TireNode676): boolean {
    if (pos === word.length) {
      return node.isWord && n === 0;
    }
    // 当前位置存在字符
    if (
      node.children.has(word[pos]) &&
      this._search(word, pos + 1, n, node.children.get(word[pos]))
    ) {
      return true;
    }
    // 当前位置不存在字符，则全部查找
    if (n > 0) {
      const keys = node.children.keys();
      for (let key of keys) {
        if (word[pos] === key) continue;
        if (this._search(word, pos + 1, n - 1, node.children.get(key))) return true;
      }
    }
    return false;
  }
  search(word: string, n: number): boolean {
    return this._search(word, 0, n, this.root);
  }
}
class MagicDictionary {
  public tire: Tire676;
  constructor() {
    this.tire = new Tire676();
  }

  buildDict(dictionary: string[]): void {
    for (let word of dictionary) {
      this.tire.insert(word);
    }
  }

  search(searchWord: string): boolean {
    return this.tire.search(searchWord, 1);
  }
}

/**
 * Your MagicDictionary object will be instantiated and called as such:
 * var obj = new MagicDictionary()
 * obj.buildDict(dictionary)
 * var param_2 = obj.search(searchWord)
 */
// @lc code=end
